1. Field of the Invention
The present invention relates to the design of lock-free data structures within computer systems. More specifically, the present invention relates to a method and apparatus for performing lock-free updates to nodes in a linked list.
2. Related Art
Operations on linked lists become more complicated in a multi-threaded environment, because concurrently executing threads can potentially interfere with each other while accessing the same linked list. In order to prevent such interference, some linked list implementations use locks to prevent different threads from interfering with each other. Unfortunately, locks often cause processes to stall, which can lead to significant performance problems, especially in systems that support large numbers of concurrently executing processes.
Because of the performance problems that arise from locks, a number of researchers have developed “lock-free” data structures, such as linked lists, that operate efficiently in a multi-threaded environment. Harris describes a way to build and modify a lock-free linked list that can be constructed using only load-linked (LL)/store-conditional (SC) or compare-and-swap (CAS) instructions (see Timothy L. Harris, “A Pragmatic Implementation of Non-Blocking Linked-Lists,” Proceedings of the 15th International Symposium on Distributed Computing, October 2001, pp. 300-14). Michael uses a variant of the Harris linked-list as the underlying structure for a lock-free hash table (see Maged M. Michael, “High Performance Dynamic Lock-Free Hash Tables and List-Based Sets,” The 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 73-82, August 2002).
Unfortunately, in the above-described lock-free linked list designs, the linked lists are used only as sets—the fields inside their constituent nodes cannot be altered in a lock-free manner. This makes such linked lists (as well as more complex data structures formed from them) less useful in applications where nodes within the linked lists have fields (other than the next-node pointers that form the lists) that logically require changing. Consequently, nodes in the above-described lock-free linked lists can be inserted, searched for, deleted, but NOT altered.
Hence, what is needed is a method and an apparatus for performing lock-free updates to fields within nodes in a lock-free linked list.